package leetcode100;

// TODO 双向循环链表 + 哈希表 [经典] 【-】 LRU 缓存

import java.util.HashMap;

public class lc100_0146 {

}

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, BNode> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private BList bList;
    // 最大容量
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        bList = new BList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            BNode node = map.get(key);
            bList.remove(node);
            bList.putLast(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        BNode newNode = new BNode(key, value);
        if (map.containsKey(key)) {  // key 已经存在于 IMap 中
            bList.remove(map.get(key));
            map.remove(key);
        } else if (cap == bList.size()) {
            // key 不存在, 并且 BiList 存满了, 启动淘汰机制
            BNode node = bList.removeFirst();
            map.remove(node.key);
        }
        bList.putLast(newNode);
        map.put(key, newNode);
    }
}

class BNode {
    public int key, val;
    public BNode next, prev;
    public BNode(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

class BList {
    // 头尾虚节点
    private BNode head, tail;
    // 链表元素数
    private int size;

    public BList() {
        // 初始化双向链表的数据
        head = new BNode(0, 0);
        tail = new BNode(0, 0);
        head.next = tail;
        head.prev = tail;
        tail.prev = head;
        tail.next = head;
        size = 0;
    }

    // 在链表尾部添加节点 x，时间 O(1)
    public void putLast(BNode x) {
        x.next = tail;
        x.prev = tail.prev;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // 删除链表中的 x 节点（x 一定存在）
    // 由于是双链表且给的是目标 Node 节点，时间 O(1)
    public void remove(BNode x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // 删除链表中第一个节点，并返回该节点，时间 O(1)
    public BNode removeFirst() {
        if (head.next == tail)
            return null;
        BNode first = head.next;
        remove(first);
        return first;
    }

    // 返回链表长度，时间 O(1)
    public int size() { return size; }

}